//018. 最大和的路径 I
//        从以下这个三角形的顶部开始，向相邻的下一行的数字移动，经过之数所能得到的最大的和
//        为 23，即：3+7+4+9=23
//        找出从以下三角形的顶端走到底端的最大总和。
//        答案：1074
//private int[][] triangle = { // Mutable
//        {75},
//        {95,64},
//        {17,47,82},
//        {18,35,87,10},
//        {20, 4,82,47,65},
//        {19, 1,23,75, 3,34},
//        {88, 2,77,73, 7,63,67},
//        {99,65, 4,28, 6,16,70,92},
//        {41,41,26,56,83,40,80,70,33},
//        {41,48,72,33,47,32,37,16,94,29},
//        {53,71,44,65,25,43,91,52,97,51,14},
//        {70,11,33,28,77,73,17,78,39,68,17,57},
//        {91,71,52,38,17,14,91,43,58,50,27,29,48},
//        {63,66, 4,68,89,53,67,30,73,16,69,87,40,31},
//        { 4,62,98,27,23, 9,70,98,73,93,38,53,60, 4,23},
//        };
public class Week018 {
    //经典数字金字塔dp
    //特别判断边界
    private static int[][] triangle = { // Mutable
            {75},
            {95, 64},
            {17, 47, 82},
            {18, 35, 87, 10},
            {20, 4, 82, 47, 65},
            {19, 1, 23, 75, 3, 34},
            {88, 2, 77, 73, 7, 63, 67},
            {99, 65, 4, 28, 6, 16, 70, 92},
            {41, 41, 26, 56, 83, 40, 80, 70, 33},
            {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
            {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
            {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
            {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
            {63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
            {4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23},
    };

    static void run() {
        int rows = triangle.length;
        for (int i = 1; i < rows; ++i) {
            int len = triangle[i].length - 1;
            //单独处理该行最左及最右的值
            triangle[i][0] += triangle[i - 1][0];
            triangle[i][len] += triangle[i - 1][len - 1];
            for (int j = 1; j < len; ++j) {
                triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
            }
        }
        int ans = 0;
        for (int i = 0, len = triangle[--rows].length; i < len; ++i) {
            if (triangle[rows][i] > ans) ans = triangle[rows][i];
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
